libreoj 10051 「一本通 2.3 例 3」Nikitosh 和异或

发表于 | 阅读次数：
本文字数： 904 字 | 阅读时长 ≈ 4 分钟

题意简述

给一个长度为 $n$ 的序列 $a_1,a_2…a_n$，求两个区间 $[l_1,r_1],[l_2,r_2]$，使得两端区间不相交，且两端区间的异或和加起来最大。

$n\le 10^5$，每个 $a_i\le 10^9$。

思路

设 $s_i$ 为前缀 $i$ 个的异或和。那么 $[l,r]$ 的异或和相当于 $s_r\oplus s_{l-1}$（$\oplus$ 表示异或）。

设 $pre[i]$ 表示在 $[1,i]$ 中区间的异或和的最大值。$suf[i]$ 表示 $[i,n]$ 中区间的异或和的最大值。那么答案就是 $max\{pre[i]+suf[i+1]\},1\le i\le n-1$。

然后 $pre$ 和 $suf$ 求法基本相同，如果会求 $pre$，只要反过来求一遍就能求出 $suf$ 了。

然后我们可以用 01-TRIE 求出必须以 $i$ 为右端点的最大区间异或和。然后求一个前缀最大值，就能得到 $pre$ 数组了。

如何求（会的跳过）

点击

假设我们当前有一些数。我们把它二进制拆分成 $32$ 位，然后从高到低插入 TRIE 树中。

现在我们要查询，这些数中哪个和 $x$ 异或起来最大。

我们把 $x$ 也拆开，对于当前这一位 $x[i]$（其值为 $0/1$），如果有一个儿子编号和 $x[i]$ 不同，尽量往不同的这里走，并且答案加上 $2^i$。否则就只能走相同的那一条边了，因为相同的异或起来为 $0$，所以这时对答案没有贡献。

我们把 $s[0,1,2\cdots i-1]$ 都插入到 TRIE 树中，然后查询必须选 $s[i]$ 的答案，就能得到以 $i$ 为右端点的最大区间异或和。然后求一遍前缀最大值，就能得到 $pre$ 数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 10000007
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	void R1(int &x)
	{
	    x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    x=(f==1)?x:-x;
	}
	void Rd(int cnt,...)
	{
	    va_list args;
	    va_start(args,cnt);
	    F(i,1,cnt) 
	    {
	        int* x=va_arg(args,int*);R1(*x);
	    }
	    va_end(args);
	}
	class Trie
	{
	public:
		int ch[N][2]; //01-TRIE 树，儿子编号开 0/1 即可
		int tot;
		void Init(){FK(ch); tot=0;}
		void Insert(int x)
		{
			int cur=0;
			D(i,30,0) 
			{
				int id=((x>>i)&1);
				if (!ch[cur][id]) ch[cur][id]=++tot;
				cur=ch[cur][id];
			}
		}
		int  Query(int x)
		{
			int cur=0;int ans=0;
			D(i,30,0)
			{
				int id=((x>>i)&1);
				if (ch[cur][id^1]) cur=ch[cur][id^1],ans|=(1<<i);
				else if (ch[cur][id]) cur=ch[cur][id];
				else return 0;
			}
			return ans;
		}
	}T;

	int n,a[N];
	void Input()
	{
		R1(n); F(i,1,n) R1(a[i]);
	}
	int L[N],R[N];
	void Soviet()
	{
		T.Init();
		F(i,1,n) 
		{
			L[i]=max(L[i-1],T.Query(a[i])); // 一边求答案，一边求了前缀最大值
			T.Insert(a[i]);
		}

		T.Init(); //注意每次都要把树清空一下
		D(i,n,1)
		{
			R[i]=max(R[i+1],T.Query(a[i]));
			T.Insert(a[i]);
		}

		long long ans=0;
		F(i,1,n) ans=max(ans,1ll*L[i]+1ll*R[i+1]);
		printf("%lld\n",ans);
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w